发现自己完全不会这两个算法,于是来学一学.
Miller Rabin 算法
用于判定一个较大的数是否为素数.
朴素的判定方法是枚举 $\sqrt n$ 内的所有数,依次检验它们是否为 $n$ 的因子,时间复杂度 $O(\sqrt n)$ .
费马小定理
对于任意素数 $p$ 以及 $1\le x\le p-1$ 的整数 $x$ ,有 $x^{p-1} \equiv 1\pmod p$.
任意 $1\le x\le p-1$ 满足 $x^{p-1} \equiv 1\pmod p$ 是 $p$ 为素数的必要条件,但不是充分条件.
一个反例是 $561=3\times 11\times 17$ ,这种数被称为卡迈克尔数.
于是我们不能直接用费马小定理来判定一个数的素性,但可以利用费马小定理先排除掉一些合数.
二次探测定理
对于任意素数 $p$ ,若 $x^2 \equiv 1\pmod p$ ,则 $x \equiv 1\pmod p$ 或 $x\equiv p-1 \pmod p$ .
这个定理也可以用来排除掉一些合数.
算法流程
记需要判定的数为 $n$ .
取若干个素数作为基底,依次用于检验,若 $n$ 通过了所有的检验,我们就认定 $n$ 为素数.
记当前用于判定的基底为 $b$ .
首先,用费马小定理检验一次,即检查是否有 $b^{n - 1} \equiv 1\pmod n$ ,若不满足,则 $n$ 为合数.
否则,若 $n-1$ 为偶,我们可以将上式变为 $(b^{\frac{n-1}2})^2 \equiv 1 \pmod n$ .
根据二次探测定理,需要检查是否有 $b^{\frac{n-1}2} \equiv 1\pmod n$ 或 $b^{\frac{n-1}2} \equiv n-1\pmod n$ ,若都不满足,则 $n$ 为合数.
如果 $\frac {n-1}{2}$ 也是个偶数,且 $b^{\frac{n-1}2} \equiv 1\pmod n$ ,就可以继续拆,变成 $(b^{\frac{n-1}4})^2 \equiv 1 \pmod n$ 继续检验.
当做到次数为奇数,或出现了 $b^{k}\equiv n-1\pmod n$ ,就无法继续用这个基底检验了.
此时退出,用下个基底继续检验,直到判定出 $n$ 为合数,或通过了所有基底的检验.
一个基底的错误概率约为 $\frac 1 4$ ,取前 $9$ 个质数分别作为基底可基本保证正确性.
时间复杂度为 $O(\log^2 n)$ ,瓶颈在于做了 $O(\log n)$ 次检验,每次检验需要计算一次快速幂,空间复杂度 $O(1)$ .
实现时可以去掉那次费马小定理的检验,因为第一次用二次探测定理检验时就已经包含了这次检验.
Pollard Rho 算法
用于找出一个较大数的某个非平凡因子.假设需要被分解的数为 $n$ ,且其最小质因子为 $p\ (p\neq n)$ .
该算法可以在 $O(\sqrt p\cdot \log n)$ 的期望时间复杂度内找出 $n$ 的某个非平凡因子,空间复杂度 $O(1)$ .
若要对 $n$ 进行质因数分解,则将得到的两个因数继续调用该算法分解,直到得到质数.
算法流程
设需要分解的数为 $n$ ,先用 Miller Rabin 算法判断 $n$ 是否为质数,若为质数,则直接返回.
否则,设有 $n = p\times q$ ,其中 $p$ 是 $n$ 的某个非平凡因子.
我们在模意义下生成一个近似随机的数列 ${x_n},x_1 = 2, x_i = f(x_{i-1}) \bmod n$ .
其中 $f$ 是一个伪随机函数,可取 $f(x) = x^2 + a$ ,其中 $a$ 为某个常数.
此时,另一个数列 ${x_n\bmod p}$ 也客观存在,而这两个数列显然都存在循环节.
根据生日悖论,数列 ${x_n}$ 循环节出现的位置期望为 $O(\sqrt n)$ ,数列 ${x_n\bmod p}$ 循环节出现的位置期望为 $O(\sqrt p)$ .
若存在两个位置 $i,j$ 使得 $x_i\equiv x_j \pmod p$ 且 $x_i \neq x_j$ ,就可以找到一个非平凡因子 $\gcd(x_i-x_j,n)$
可以取 $i,2i$ 这两个位置,其中 $x_{2i}$ 的值可以通过每次迭代两步得到,类似于 floyd 消圈,而不用存储整个数列.
计算出 $t =\gcd(x_{i}-x_{2i},n)$ ,若 $t=1$ ,说明 $i,2i$ 不在任何数列的循环节对应位置,继续枚举下一个 $i$ .
若 $t = n$ ,说明 $i,2i$ 同时在两个数列的对应位置,那么再增大 $i$ 也无法找到仅在一个数列中对应的 $i$ .
此时只能退出,更换随机函数 $f(x)$ ,即取另一个常数 $a$ 执行算法.
若 $t\neq 1$ 且 $t\neq n$ ,那么我们就找到了 $t$ 作为 $n$ 的一个非平凡因子.
由于函数 $f(x)=x^2 +a$ 只会生成模 $4$ 意义下与 $a,a+1$ 同余的数,所以无法分解出 $2$ 这个因子,需要特判.
期望需要枚举 $O(\sqrt p)$ 个 $i$ 来找到一个非平凡因子,每次需要求一次 $\gcd$ ,时间复杂度 $O(\sqrt p\cdot \log n)$ .
当 $n$ 不为素数时, $n$ 的最小质因子显然不超过 $\sqrt n$ ,于是时间复杂度可以化为 $O(n^{\frac 1 4}\cdot \log n)$ .
优化
注意到我们只有在 $\gcd(x_i-x_{2i},n) = 1$ 的情况下才会继续运行该算法.
我们设置一个参数 $k$ ,计算每 $k$ 个 $x_i-x_{2i}$ 的乘积对 $n$ 取模的结果 $prod$ .
若 $\gcd(prod,n) =1$ ,说明这 $k$ 个 $x_i-x_{2i}$ 与 $n$ 的 $\gcd$ 均为 $1$ ,继续考虑接下来的 $k$ 个 $x_i-x_{2i}$ .
若 $\gcd(prod,n) = n$ ,我们不知道这 $k$ 个数中是否有解,此时只能回到 $k$ 步前,运行原本的 Pollard Rho 算法.
若 $\gcd(prod,n)\neq 1$ 且 $\gcd(prod,n)\neq n$ ,那么 $\gcd(prod,n)$ 就是 $n$ 的一个非平凡因子.
此时,该算法找出一个非平凡因子的时间复杂度被优化到了 $O(n^{\frac 1 4}+\frac{n^{\frac 1 4}\log n}{k}+k\log n)$ .